'''
1.给一个二维矩阵，0代表水，1代表陆地，求当前所有陆地到水的最近的距离分别是多少？
输入：
 0 0 1
 1 0 1
 0 1 1
 1 1 1
 输出：
 0 0 1
 1 0 1
 0 1 2
 1 2 3
'''
import unittest
from collections import deque
from typing import List

def validate_matrix(matrix: List[List[int]]) -> bool:
    """
    验证输入矩阵的有效性。

    Args:
        matrix: 二维整数列表

    Returns:
        bool: 矩阵是否有效

    Raises:
        ValueError: 如果矩阵格式或内容无效
    """
    if not isinstance(matrix, list) or not all(isinstance(row, list) for row in matrix):
        raise ValueError("输入必须是列表的列表")
    
    if not matrix or not matrix[0]:
        return False

    rows, cols = len(matrix), len(matrix[0])
    if not all(len(row) == cols for row in matrix):
        raise ValueError("所有行必须具有相同的长度")

    if not all(all(x in [0, 1] for x in row) for row in matrix):
        raise ValueError("矩阵元素必须为0或1")

    return True

def initialize_distance_matrix(matrix: List[List[int]]) -> tuple:
    """
    初始化距离矩阵和队列。

    Args:
        matrix: 输入矩阵

    Returns:
        tuple: (距离矩阵, 队列)
    """
    rows, cols = len(matrix), len(matrix[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    queue = deque()

    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 0:
                dist[i][j] = 0
                queue.append((i, j))

    return dist, queue

def update_distances_bfs(dist: List[List[int]], queue: deque) -> List[List[int]]:
    """
    使用BFS更新距离矩阵。

    Args:
        dist: 距离矩阵
        queue: 包含初始位置的队列

    Returns:
        List[List[int]]: 更新后的距离矩阵
    """
    rows, cols = len(dist), len(dist[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        x, y = queue.popleft()
        current_dist = dist[x][y] + 1
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and dist[nx][ny] > current_dist:
                dist[nx][ny] = current_dist
                queue.append((nx, ny))

    return dist

def update_matrix(matrix: List[List[int]]) -> List[List[int]]:
    """
    计算矩阵中每个元素到最近的0的距离。

    Args:
        matrix: 二维整数列表，元素为0或1

    Returns:
        List[List[int]]: 距离矩阵

    Raises:
        ValueError: 如果输入矩阵无效
    """
    try:
        if not validate_matrix(matrix):
            return []

        dist, queue = initialize_distance_matrix(matrix)
        dist = update_distances_bfs(dist, queue)

        return dist
    except ValueError as e:
        print(f"输入验证错误: {e}")
        return []
    except Exception as e:
        print(f"计算过程中发生错误: {e}")
        return []

class TestUpdateMatrix(unittest.TestCase):
    """单元测试类"""
    
    def test_valid_matrix(self):
        matrix = [
            [0, 0, 1],
            [1, 0, 1],
            [0, 1, 1],
            [1, 1, 1]
        ]
        expected = [
            [0, 0, 1],
            [1, 0, 1],
            [0, 1, 2],
            [1, 2, 3]
        ]
        self.assertEqual(update_matrix(matrix), expected)
    
    def test_empty_matrix(self):
        self.assertEqual(update_matrix([]), [])
    
    def test_invalid_matrix(self):
        matrix = [
            [0, 2, 1],
            [1, 0, 1]
        ]
        with self.assertRaises(ValueError):
            update_matrix(matrix)
    
    def test_all_zeros(self):
        matrix = [
            [0, 0],
            [0, 0]
        ]
        expected = [
            [0, 0],
            [0, 0]
        ]
        self.assertEqual(update_matrix(matrix), expected)
    
    def test_all_ones(self):
        matrix = [
            [1, 1],
            [1, 1]
        ]
        expected = [
            [float('inf'), float('inf')],
            [float('inf'), float('inf')]
        ]
        self.assertEqual(update_matrix(matrix), expected)

if __name__ == "__main__":
    # 示例用法
    matrix = [
        [0, 0, 1],
        [1, 0, 1],
        [0, 1, 1],
        [1, 1, 1]
    ]
    
    print("输入矩阵:")
    for row in matrix:
        print(row)
    
    result = update_matrix(matrix)
    
    print("\n距离矩阵:")
    for row in result:
        print(row)
    
    # 运行单元测试
    print("\n运行单元测试...")
    unittest.main(argv=['first-arg-is-ignored'], exit=False)